Sim is a pencil-and-paper game that is played by two players.

Gameplay

Six dots ('vertices') are drawn. Each dot is connected to every other dot by a line ('edge'). Two players take turns coloring any uncolored lines. One player colors in one color, and the other colors in another color, with each player trying to avoid the creation of a triangle made solely of their color (only triangles with the dots as corners count; intersections of lines are not relevant); the player who completes such a triangle loses immediately.

Analysis

Ramsey theory Ramsey theory, named after the British mathematician and philosopher Frank P. Ramsey, is a branch of mathematics that focuses on the appearance of order in a substructure given a structure of a known size. Problems in Ramsey theory typically ask a ...

can also be used to show that no game of Sim can end in a tie. Specifically, since the '' Ramsey number'' ''R''(3,3)=6, any two-coloring of the

complete graph In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge. A complete digraph is a directed graph in which every pair of distinct vertices is c ...

on 6 vertices (K₆) must contain a monochromatic triangle, and therefore is not a tied position. This will also apply to any super-graph of K₆. For another proof that there must eventually be a triangle of either color, see the

Theorem on friends and strangers The theorem on friends and strangers is a mathematical theorem in an area of mathematics called Ramsey theory. Statement Suppose a party has six people. Consider any two of them. They might be meeting for the first time—in which case we will ...

. Computer search has verified that the second player can win Sim with perfect play, but finding a perfect strategy that humans can easily memorize is an open problem. The game of Sim is one example of a Ramsey game. Other Ramsey games are possible. For instance, the players can be allowed to color more than one line during their turns. Another Ramsey game similar to Sim and related to Ramsey number ''R''(4,4)=18, which again cannot end in a tie, is played on 18 vertices and the 153 edges between them. The two players must avoid to color a monochromatic

tetrahedron In geometry, a tetrahedron (plural: tetrahedra or tetrahedrons), also known as a triangular pyramid, is a polyhedron composed of four triangular faces, six straight edges, and four vertex corners. The tetrahedron is the simplest of all the o ...

(a three-dimensional pyramid with four triangular faces). The Ramsey number ''R''(3,3,3)=17 implies that any three-coloring of the complete graph on 17 vertices must contain a

monochromatic A monochrome or monochromatic image, object or color scheme, palette is composed of one color (or lightness, values of one color). Images using only Tint, shade and tone, shades of grey are called grayscale (typically digital) or Black and wh ...

triangle. A corresponding Ramsey game uses pencils of three colors. One approach can have three players compete, while another would allow two players to alternately select any of the three colors to paint an edge of the graph, until a player loses by completing a monochromatic triangle. Finding perfect winning strategies for these variants is most likely out of reach. A technical report''Graph Ramsey Games'' by Wolfgang Slany
at

arXiv arXiv (pronounced "archive"—the X represents the Greek letter chi ⟨χ⟩) is an open-access repository of electronic preprints and postprints (known as e-prints) approved for posting after moderation, but not peer review. It consists of ...

by Wolfgang Slany is available online, with many references to literature on Sim, going back to the game's introduction by

Gustavus Simmons Gustavus J. Simmons (born 1930) is a retired cryptographer and former manager of the applied mathematics Department and Senior Fellow at Sandia National Laboratories. He worked primarily with authentication theory, developing cryptographic techni ...

in 1969,Simmons, Gustavus J. "The game of SIM," ''J. Recreational Mathematics'', 2(2), 1969, pp. 66. including proofs and estimates of the difficulty as well as

computational complexity In computer science, the computational complexity or simply complexity of an algorithm is the amount of resources required to run it. Particular focus is given to computation time (generally measured by the number of needed elementary operations) ...

of Sim and other Ramsey games.

Software

A self-improving

Java applet Java applets were small applications written in the Java programming language, or another programming language that compiles to Java bytecode, and delivered to users in the form of Java bytecode. The user launched the Java applet from a ...

including its source code is availableJava applet page, including source code
/ref> for online play against a computer program. An app including its source code in the visual multi-platform

Catrobat Catrobat is a block-based visual programming language and Open Source Software non-profit project. The first release dates back to 2010 and was initiated by Wolfgang Slany from the Technical University Graz in Austria. The multidisciplinary team ...

programming language is availableApp for smartphones, including source code
/ref> for playing it against one's smartphone. An electronic version is available at: https://wideaperture.net/sim/

References

{{reflist Ramsey theory Mathematical games Combinatorics Combinatorial game theory Paper-and-pencil games Solved games Positional games